package coin.yang;

import java.util.Objects;

public class ListEx {
    public static void main(String[] args) {

        ArrList<String> list = new ArrList<>(0);
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("a");
        list.add("e");
        list.add("f");
        list.add("a");
        list.add("g");
        ArrList<String> list2 = new ArrList<>(0);
        list2.add("b");
        list2.add("c");
        list2.add("d");
        list2.add("a");
        list2.add("e");
        list2.add("f");
        list2.add("a");
        list2.add("g");
        // list.add(0, "h");
        // list.add(1, "i");
        // list.add(4, "j");
        // list.add(10, "k");
        // list.remove(6);
        // int index = list.indexOf("a");
        // System.out.println(index);
        // list.remove("a");
        System.out.println(list.equals(list2));
        // 截取子列表
        ArrList<String> sub = list.subList(2, 5);
        System.out.println(sub);
        System.out.println(list);
        ArrList<Integer> list3 = new ArrList<>();
        System.out.println(list3);

    }

}

// 实现ArrayList
class ArrList<E> {

    // 定义数组用于存储元素
    private Object[] arr;
    // 定义变量用于记录元素个数
    private int size = 0;

    public ArrList() {
        // 构建长度为10的数组
        arr = new Object[10];
    }

    public ArrList(int initialCapacity) {
        // 判断容量是否合法
        if (initialCapacity < 0)
            throw new IllegalArgumentException("容量不能小于0！！！");
        arr = new Object[initialCapacity];
    }

    // 添加元素
    public void add(E e) {
        // 判断是否需要扩容
        if (size >= arr.length)
            grow();
        // 添加元素，同时元素个数+1
        arr[size++] = e;
    }

    // 插入元素
    public void add(int index, E e) {
        // 判断下标是否越界
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        // 判断是否需要扩容
        if (size >= arr.length)
            grow();
        // 判断是否是尾部追加
        if (index != size) {
            // 从index开始，元素整体后挪
            System.arraycopy(arr, index, arr, index + 1, size - index);
        }
        // 插入元素
        arr[index] = e;
        // 元素个数+1
        size++;
    }

    // 扩容
    private void grow() {
        // 构建新数组
        Object[] newArr;
        if (arr.length <= 1) {
            newArr = new Object[size + 1];
        } else {
            // 计算新容量
            int newCapacity = arr.length + (arr.length >> 1);
            newArr = new Object[newCapacity];
        }
        // 将原来数组中的元素拷贝到新数组中
        System.arraycopy(arr, 0, newArr, 0, arr.length);
        // 将arr的地址指向改为新数组
        arr = newArr;
    }

    // 移除指定下标位置上的元素
    public void remove(int index) {
        // 判断下标是否越界
        outOfBounds(index);
        // 判断是否是尾部元素
        if (index != size - 1) {
            // 后边的元素要覆盖前面的元素
            System.arraycopy(arr, index + 1, arr, index, size - index - 1);
        }
        // 元素个数-1
        size--;
    }

    // 获取指定元素第一次出现的下标
    public int indexOf(E e) {
        // 遍历元素
        for (int i = 0; i < size; i++) {
            // if (arr[i] == e || arr[i] != null && arr[i].equals(e))
            if (Objects.equals(arr[i], e))
                return i;
        }
        // 如果整个循环结束，都没有返回，那么说明没有这个元素
        return -1;
    }

    // 移除指定的元素
    public void remove(E e) {
        // 获取这个元素的位置
        int index = indexOf(e);
        // 判断是否有这个元素
        if (index != -1) remove(index);
    }

    // 获取元素个数
    public int size() {
        return size;
    }

    // 判断集合是否为空
    public boolean isEmpty() {
        return size <= 0;
    }

    // 判断是否有指定元素
    public boolean contains(E e) {
        return indexOf(e) != -1;
    }

    // 清空集合
    public void clear() {
        // 将元素依次清除
        for (int i = size; i >= 0; i--) {
            arr[i] = null;
        }
        size = 0;
    }

    // 判断两个集合是否相等
    public boolean equals(Object o) {
        // 判断地址是否相同
        if (this == o) return true;
        // 判断参数是否为空
        if (o == null) return false;
        // 判断类型是否一样
        if (this.getClass() != o.getClass()) return false;
        // 转换
        ArrList list = (ArrList) o;
        // 判断元素个数是否一样
        if (this.size != list.size) return false;
        // 遍历集合，依次判断
        for (int i = 0; i < size; i++) {
            // if (!(this.arr[i] == list.arr[i] || this.arr[i] != null && this.arr[i].equals(list.arr[i])))
            // JDK1.8中，可以替换
            if (!Objects.equals(this.arr[i], list.arr[i]))
                return false;
        }
        // 整个循环结束，都没有返回，那么说明两个集合相同位置上的元素一模一样
        return true;
    }

    // 判断下标是否越界
    private void outOfBounds(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // 获取指定下标位置上的元素
    public E get(int index) {
        // 判断下标是否越界
        outOfBounds(index);
        return (E) arr[index];
    }

    // 替换指定下标位置上的元素
    public void set(int index, E e) {
        // 判断下标是否越界
        outOfBounds(index);
        arr[index] = e;
    }

    // 获取指定元素最后一次出现的下标
    public int lastIndexOf(E e) {
        // 倒序遍历
        for (int i = size - 1; i >= 0; i--) {
            // 判断元素是否相等
            if (Objects.equals(arr[i], e))
                return i;
        }
        // 如果循环结束都没有返回，说明没有这个元素
        return -1;
    }

    // 截取子列表
    public ArrList<E> subList(int fromIndex, int toIndex) {
        // 判断下标是否合法
        if (toIndex >= size || fromIndex < 0 || fromIndex > toIndex)
            throw new IllegalArgumentException("下标不合法！！！");
        // 要复制的元素个数
        int n = toIndex - fromIndex;
        // 构建子列表
        ArrList<E> sub = new ArrList<>(n);
        System.arraycopy(arr, fromIndex, sub.arr, 0, n);
        sub.size = n;
        return sub;
    }

    // 转化为字符串
    @Override
    public String toString() {
        // 判断是否有元素
        if (size <= 0) return "[]";
        // 拼接多个元素
        StringBuilder sb = new StringBuilder("[");
        // 遍历元素
        for (int i = 0; i < size; i++) {
            sb.append(arr[i]).append(", ");
        }
        // 转化为字符串
        String str = sb.toString();
        // 截取掉最后的", "
        str = str.substring(0, str.length() - 2);
        // 拼接上右半边的"]"
        str += "]";
        return str;
    }
}
